#include "gtest/gtest.h"

#include <vector>
#include <cstdlib>
#include <ctime>

#include "bubble_sort.h"
#include "insertion_sort.h"
#include "selection_sort.h"
#include "merge_sort.h"
#include "quick_sort.h"

using namespace std;
using namespace algo;


class SortTest : public testing::Test
{
protected:

	void SetUp()
	{
	}

	void TearDown()
	{
	}

public:
	bool IsOrdered(const vector<int>& vctNums);

private:
};

bool SortTest::IsOrdered(const vector<int>& vctNums)
{
	if (vctNums.size() <= 1)
	{
		return true;
	}
	
	vector<int>::const_iterator iterPrev = vctNums.begin();
	vector<int>::const_iterator iterCur = vctNums.begin();
	++iterCur;

	for (; iterCur != vctNums.end(); ++iterCur, ++iterPrev)
	{
		if (*iterCur < *iterPrev)
		{
			return false;
		}
	}
	return true;
}

void test_sort(vector<int> & vctNums)
{

	//bubble_sort(vctNums);
    //insertion_sort(vctNums);
    //selection_sort(vctNums);
    //merge_sort(vctNums);
    quick_sort(vctNums);
}

TEST_F(SortTest, HandlesInput1)
{
	vector<int> vctNums = {1, 2, 3, 4, 5};
    test_sort(vctNums);
	EXPECT_EQ(IsOrdered(vctNums), true);
}

TEST_F(SortTest, HandlesInput2)
{
	vector<int> vctNums = {5, 4, 3, 2, 1};
    test_sort(vctNums);
	EXPECT_EQ(IsOrdered(vctNums), true);
}

TEST_F(SortTest, HandlesInput3)
{
	vector<int> vctNums = {1};
    test_sort(vctNums);
	EXPECT_EQ(IsOrdered(vctNums), true);
}

TEST_F(SortTest, HandlesInput4)
{
	vector<int> vctNums = {};
    test_sort(vctNums);
	EXPECT_EQ(IsOrdered(vctNums), true);
}

TEST_F(SortTest, HandlesInput5)
{
	vector<int> vctNums = {2, 6, 2, 8, 1};
    test_sort(vctNums);
	EXPECT_EQ(IsOrdered(vctNums), true);
}

TEST_F(SortTest, HandlesInput6)
{
    vector<int> vctNums = {5, 5, 5, 5, 5};
    test_sort(vctNums);
    EXPECT_EQ(IsOrdered(vctNums), true);
}

TEST_F(SortTest, HandlesInput7)
{
    const int iRandNumSize = 10000;
    const int iTestNum = 10;
    vector<int> vctNums;
    vctNums.reserve(iRandNumSize);

    for (int j = 0; j < iTestNum; ++j)
    {
        srand((int)time(0));
        for (int i = 0; i < iRandNumSize; ++i)
        {
            vctNums.push_back(rand() % 1000);
        }
        test_sort(vctNums);
        EXPECT_EQ(IsOrdered(vctNums), true);
    }
}


int main(int argc, char **argv)
{
	::testing::InitGoogleTest(&argc, argv);
	return RUN_ALL_TESTS();
}


